 /*
  * 排序
  * */
 package com.adee.algorithm.sort;

 import java.util.ArrayList;
 import java.util.Stack;

 /**
  * https://blog.csdn.net/m0_75062065/article/details/133579950
  *
 排序算法	平均时间复杂度	    最好情况	    最坏情况	    空间复杂度	排序方式	    稳定性
 冒泡排序	O(n?)	        O(n)	    O(n?)	    O(1)	    In-place	稳定
 简单选择	O(n?)	        O(n?)	    O(n?)	    O(1)	    In-place	不稳定
 直接插入	O(n?)	        O(n)	    O(n?)	    O(1)	    In-place	稳定
 希尔排序	O(nlogn)	    O(nlog?n)	O(nlog?n)	O(1)	    In-place	不稳定
 归并排序	O(nlogn)	    O(nlogn)	O(nlogn)	O(n)	    Out-place	稳定
 快速排序	O(nlogn)	    O(nlogn)	O(n?)	    O(logn)	    In-place	不稳定
 堆排序	    O(nlogn)	    O(nlogn)	O(nlogn)	O(1)	    In-place	不稳定
 计数排序	O(n + k)	    O(n + k)	O(n + k)	O(k)	    Out-place	稳定
 桶排序	    O(n + k)	    O(n + k)	O(n?)	    O(n + k)	Out-place	稳定
 基数排序	O(n * k)	    O(n * k)	O(n * k)	O(n + k)	Out-place	稳定
 ————————————————
 排序方式的选择：
(1)若n较小(如n≤50)，可采用直接插入或直接选择排序。
    　当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。
(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；
(3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。
    　快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
    　堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。
    　若要求排序稳定，则可选用归并排序。先利用直接插入排序求得较长的有序子文件，然后再两两归并之。因为直接插入排序是          稳定的，所以改进后的归并排序仍是稳定的。
————————————————
实际应用：
1. redis中，n<7时，冒泡排序，n>=7时，快速排序
2. java

  ————————————————
  java中Arrays.sort使用了两种排序方法，jdk1.7中使用了快速排序和归并排序。jdk1.8中做了优化，使用了快速排序和TimSort。
  Collections.sort()方法和list.sort()方法都调用了Arrays.sort()方法。

  快速排序主要是对哪些基本类型数据（int,short,long等）排序， 而合并排序用于对对象类型进行排序。
  使用不同类型的排序算法主要是由于快速排序是不稳定的，而合并排序是稳定的。这里的稳定是指比较相等的数据在排序之后仍然按照排序之前
  的前后顺序排列。对于基本数据类型，稳定性没有意义，而对于对象类型，稳定性是比较重要的，因为对象相等的判断可能只是判断关键属性，
  最好保持相等对象的非关键属性的顺序与排序前一直；另外一个原因是由于合并排序相对而言比较次数比快速排序少，移动（对象引用的移动）
  次数比快速排序多，而对于对象来说，比较一般比移动耗时。
  补充一点合并排序的时间复杂度是n*logn, 快速排序的平均时间复杂度也是n*logn，但是合并排序的需要额外的n个引用的空间。

  TimSort
  由于sort()和TimSort.sort走的流程基本一致，这里只分析TimSort.sort()方法，进入该方法。
  这里有必要先说一下TimSort排序算法的核心内容，了解这个算法的核心内容有助于看下面的代码。
  TimSort的核心是这样：
  1.如果数组的长度小于32，直接采用二分法插入排序，就是下面方法中的binarySort方法实现的，这个算法原理，我举个例子大家就明白了
　　　　假设数组为：[1,3,9,6,2],二分法插入排序插入如下：
　　　　　　I：从开头先把自然升序（或降序）段找出来，那什么是自然升序段，就是没有经过排序算法，原始数据就是有序的，
        本数组中自然升序段就是1，3，9；
　　　　　　II：按照正常的思维，直接拿6，从头开始和前三个元素一个一个比较也可以实现排序，但是这样效率太低，那怎么做可以效率高点呢？
        就是我们之前高数中学的二分查找法，就是通过二分查找法，我先找到3，发现6 > 3，那我就不用和1进行比较了。

  2.如果数组的长度大于32，那就把数组拆分成一个一个的小段，每段的长度在16～32之间，使用上面介绍的二分法插入排序，把每一段进行排序，
  之后在把每一个排好序的段进行合并，最终就可以实现整个数组的排序，大致的思想就是这样，这个叙述可能会给大家一种误解，就是认为每一段
  都排好序之后在进行合并，其实不是这样的，而是每一段边排序，如果符合特定条件就会合并。

  ————————————————


  TimSort 算法为了减少对升序部分的回溯和对降序部分的性能倒退，将输入按其升序和降序特点进行了分区。排序的输入的单位不是一个个单独的数字，而是一个个的块-分区。其中每一个分区叫一个run。针对这些 run 序列，每次拿一个 run 出来按规则进行合并。每次合并会将两个 run合并成一个 run。合并的结果保存到栈中。合并直到消耗掉所有的 run，这时将栈上剩余的 run合并到只剩一个 run 为止。这时这个仅剩的 run 便是排好序的结果。


 * */
 public class Test002_Sort {
     public static void main(String[] args) {
         int[] arr = new int[]{10,33,1,8,50,6,18,2,12,20,117,8,265,310,46,92,1001,3,7,37};
         printArr(arr);
         // maopao(arr);
         // xuanze(arr);
         // charu(arr);
         // xier(arr);
         // guibing1(arr, 0, arr.length - 1);
         // guibing2(arr);
         // kuaisu1(arr, 0, arr.length-1);
         // kuaisu2(arr);
         dui(arr);
         // tong(arr);

         // stackTest();

         printArr(arr);
     }
     private static void printArr(int[] arr) {
         for(int i : arr) {
             System.out.print(i + " ");
         }
         System.out.println();
     }
     // 冒泡
     public static void maopao(int[] arr) {
         int len = arr.length;
         if(len <= 1) return;
         int tmp;
         for(int i = len; i > 0; i--) {
             for(int j = 0; j < i-1; j++) {
                 if(arr[j] > arr[j+1]) {
                     tmp = arr[j];
                     arr[j] = arr[j+1];
                     arr[j+1] = tmp;
                 }
             }
         }
     }
     // 选择
     public static void xuanze(int[] arr) {
         int len = arr.length;
         if(len <= 0) return;
         int idx;
         int tmp;
         for(int i = 0; i < len - 1; i++) {
             idx = i;
             for(int j = i + 1; j < len; j++) {
                 if(arr[idx] > arr[j]) idx = j;
             }
             if(idx != i) {
                 tmp = arr[i];
                 arr[i] = arr[idx];
                 arr[idx] = tmp;
             }
         }
     }
     // 插入
     public static void charu(int[] arr) {
         int len = arr.length;
         if(len <= 0) return;
         int temp;
         for(int i = 1; i < len; i++) {
             temp = arr[i];
             int j = i -1;
             while(arr[j] > temp) {
                 arr[j+1] = arr[j];
                 if(j-- == 0) break;
             }
             arr[j+1] = temp;
         }
     }
     // 希尔（复杂插入）
     public static void xier(int[] arr) {
         int len = arr.length;
         int k = 5; // gap
         int idx;
         int tmp;
         do {
             for(int i = 0; i < k; i++) {
                 for(int j = i + k; j < len; j = j + k) {
                     tmp = arr[j];
                     int m = j - k;
                     while(m >= 0 && arr[m] > tmp) {
                         arr[m + k] = arr[m];
                         m = m - k;
                     }
                     arr[m + k] = tmp;
                 }
             }
         } while((k = k/2) >= 1);
     }
     // 归并
     // 递归实现
     public static void guibing1(int[] arr, int begin, int end) {
         // System.out.println("begin:" + begin + ", end:" + end);
         if(begin == end) return;
         int m = (begin + end) / 2;
         guibing1(arr, begin, m);
         guibing1(arr, m + 1, end);
         merge(arr, begin, m, end);
     }
     // 将arr数组的两个有序子序列，即下标begin~m和m+1~end两个子序列从小到大排序
     public static void merge(int[] arr, int begin, int m, int end) {
         if(begin >= end) return;
         int i = begin, j = m + 1, k = begin;
         int[] arrRet = new int[end - begin + 1];
         while(i <= m && j <= end) {
             if(arr[i] <= arr[j]) {
                 arrRet[k++] = arr[i++];
             } else {
                 arrRet[k++] = arr[j++];
             }
         }
//        while(i <= m) {
//            arrRet[k++] = arr[i++];
//        }
//        while(j <= end) {
//            arrRet[k++] = arr[j++];
//        }
//        for(int a = begin; a <= end; a++) {
//            arr[a] = arrRet[a];
//        }
         // printArr(arrRet);
         if(i > m && j <= end) {
             System.arraycopy(arr, j, arrRet, k, end - j + 1);
         } else if(j > end && i <= m) {
             System.arraycopy(arr, i, arrRet, k, m - i + 1);
         } else if(i < m && j < end) {
             System.out.println("error...>>");
         }
         System.arraycopy(arrRet, begin, arr, begin, end - begin + 1);
     }
     // 循环实现
     public static void guibing2(int[] arr) {
         int len = arr.length;
         if(len <= 1) return;
         int gap = 1;
         int i;
         while(gap <= len) {
             i = 0;
             do {
                 int m = i + gap -1;
                 int end = (i + 2*gap - 1) > (len - 1) ? (len - 1) : (i + 2*gap - 1);
                 // System.out.println("    >> begin:" + i + ", m:" + m + ", end:" + end);
                 merge(arr, i, m, end);
                 // printArr(arr);
                 i = end + 1;
             } while(len-i > gap); // 剩余元素个数大于gap
             gap *= 2;
         }
     }

     // 快速
     // 递归实现
     public static void kuaisu1(int[] arr, int low, int high) {
         if(low >= high) return;
         int lowOld = low;
         int highOld = high;
         int base = arr[low];
         while(low < high) {
             while(low < high && arr[high] >= base) high--;
             if(arr[high] < base) {
                 arr[low] = arr[high];
             }
             while(low < high && arr[low] < base) low++;
             if(arr[low] >= base) {
                 arr[high] = arr[low];
             }
         }
         if(low == high) arr[low] = base;
         System.out.println("排序后low:" + low + ", high:" + high);
         printArr(arr);
         kuaisu1(arr, lowOld, low);
         kuaisu1(arr, low+1, highOld);
     }
     // 循环实现
     public static void kuaisu2(int[] arr) {
         int len = arr.length;
         if(len <= 1) return;
         Stack<Integer> lowHighStack = new Stack();
         lowHighStack.push(0); // low
         lowHighStack.push(len - 1); // high
         while(!lowHighStack.empty()) {
             int iHigh = lowHighStack.pop();
             int iLow = lowHighStack.pop();
             if(iHigh == iLow) continue;
             int m = mergeKuaisu(arr, iLow, iHigh);
             lowHighStack.push(iLow);
             lowHighStack.push(m);
             lowHighStack.push(m + 1 > iHigh ? iHigh : m + 1);
             lowHighStack.push(iHigh);
             printArr(arr);
         }
     }
     // 一次对low~high区间进行快速排序的迭代，返回基准数的位置索引
     public static int mergeKuaisu(int[] arr, int low, int high) {
         if(low >= high) return low;
         int base = arr[low];
         while(low < high) {
             while(low < high && arr[high] >= base) high--;
             if(arr[high] < base) {
                 arr[low] = arr[high];
             }
             while(low < high && arr[low] < base) low++;
             if(arr[low] >= base) {
                 arr[high] = arr[low];
             }
         }
         if(low == high) arr[low] = base;
         return low;
     }
     public static void stackTest() {
         Stack s = new Stack();
         s.push(2);
         s.push(5);
         s.empty();
         System.out.println(s.pop());
         System.out.println(s.pop());
         System.out.println(s.pop());
     }
     // 堆排序，对于顺序存储结构

     /**
      * 堆排序，排序思想
      * 1.首先将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是堆结构的顶端;
      * 2.将顶端的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组个数为n-1;
      * 3.将剩余的n-1个数再构造成大根堆，再将顶端数与n-1位置的数交换，如此反复执行，便能得到有序数组;
      * 注意:升序用大根堆，降序就用小根堆(默认为升序).
      */
     public static void dui(int[] arr) {
         int len = arr.length;
         // 首先，将数组arr构造为一个大顶堆
         // len / 2 - 1 是arr数组作为完全二叉树的第一个非叶节点
         for(int i = len / 2 - 1; i >= 0; i--) {
             adjust3(arr, i, len);
         }
         System.out.println("初始化大顶堆得到：");
         printArr(arr);
         // 将大顶堆的顶元素与叶节点元素互换，再将新的顶元素下沉到合适的位置，以便使新的子数组仍为大顶堆
         for(int j = len - 1; j > 0; j--) {
             swap(arr, 0, j);
             adjust3(arr, 0, j );

         }
     }
     // 假定下标为parent的元素的两个子节点都已经是大顶堆了，此时将parent元素下沉到合适位置，以使parent作为顶点的完全二叉树也是一个大顶堆
     // 大顶堆（小顶堆）就是一个符合完全二叉树的数组（顺序排列）
     // 将以parent为顶点，及其左右两个子节点三个元素中最大值调整到顶点，并将原顶点值调整下来，
     // 最终效果是：在完全二叉树中，若顶点值与叶节点的值互换，则将互换后的这个顶点值下沉到合适位置，以保证仍然是一个完全二叉树
     public static void adjust3(int[] arr, int parent, int length) {
         int tmp = arr[parent], bigger, left, right;
         while (parent < length) {
             left = parent*2+1;
             right = left + 1;
             if (left >= length) { // parent此时为叶节点
                 arr[parent] = tmp;
                 break;
             } else if (right >= length) {
                 bigger = left;
             } else {
                 bigger = arr[left] >= arr[right] ? left : right;
             }
             if (tmp >= arr[bigger]) {
                 arr[parent] = tmp;
                 break;
             } else {
                 arr[parent] = arr[bigger];
                 parent = bigger;
             }
         }
     }
     // 桶排序
     public static void tong(int[] arr) {
         int buckets = arr.length >> 3 + 1; // 桶个数
         ArrayList bucket[] = new ArrayList[buckets];
         for (int i = 0; i < bucket.length; i++) {
             bucket[i] = new ArrayList<Integer>();// 确定桶的格式为ArrayList
         }
         for (int i = 0; i < arr.length; i++) {
             int index = arr[i] >> 3;// 确定元素存放的桶号
             bucket[index].add(arr[i]);// 将元素存入对应的桶中
         }
         for (int i = 0; i < bucket.length; i++) {// 遍历每一个桶
             bucket[i].sort(null);// 对每一个桶排序
//            for (int i1 = 0; i1 < bucket[i].size(); i1++) {// 遍历桶中的元素并输出
//                System.out.print(bucket[i].get(i1) + " ");
//            }
         }
     }



     public static void swap(int[] arr, int i, int j) {
         int temp = arr[i];
         arr[i] = arr[j];
         arr[j] = temp;
     }
 }
